Survey on progresses in dynamic matchings
September 4, 2024 (GHC 4405)
Abstract: This talk discusses the dynamic matching problem, which seeks to maintain a large matching / small vertex cover in a graph undergoing edge insertions/deletions. It covers recent progresses on maintaining $(1 + \epsilon)$-approximations in unweighted bipartite graphs. The two main topics of focus are sparsification and MWU based reductions to vertex-dynamic cases with larger errors, and connections with Rusza-Szemeredi graphs and the online matrix-vector multiplication conjecture in such settings.